Contents of a distributed database may reside on a plurality of storage servers. In an illustrative example, a distributed database may be represented by a horizontally partitioned database, in which plurality of database records are split between multiple storage servers based on, e.g., a primary key. A horizontal database partition may be referred to as a “shard,” and a horizontally partitioned database may be referred to as “sharded database.” In another illustrative example, a distributed database may be represented by a vertically partitioned database, in which the database tables are split by columns, such that each database record would be distributed over multiple storage servers.